#include<iostream>
using namespace std;
class Node {
public:
    int val;
    Node* left;
    Node* right;

    Node() {}

    Node(int _val) {
        val = _val;
        left = NULL;
        right = NULL;
    }

    Node(int _val, Node* _left, Node* _right) {
        val = _val;
        left = _left;
        right = _right;
    }
};

class Solution {
public:
    Node *head, *pre=NULL;
    Node* treeToDoublyList(Node* root) {
        if (root == NULL)return NULL;
        inorder(root);
        head->left = pre;
        pre->right = head;
        return head;

        
    }
    void inorder(Node* node){
        if(node == NULL)return;
        //左树
        inorder(node->left);
        //操作
        if (pre==NULL)head=node;
        else if (pre!=NULL)
        {
            pre->right = node;
            node->left = pre;
        }
         pre = node;
        
        //右树
        inorder(node->right);

    }
};